The present invention relates generally to content addressable memories (CAMs) and more particularly to approaches for ordering entries in a ternary CAM.
Information network systems continue to proliferate. In a typical network system, data can transferred in data structures referred to as xe2x80x9cpackets.xe2x80x9d A packet can travel through network according to information included in a portion of the packet referred to as a xe2x80x9cheader.xe2x80x9d Network switches and/or routers can receive packets, extract information from the packet header, and process the packet according to the extracted information. Network header information can establish, to name just a few possible examples, the destination of a packet and/or the manner in which a packet should be transmitted.
Packet routing and/or switching typically utilizes a matching function. In a matching function, a header field will be compared to a number of entries. In the event the field (or a portion of the field) matches an entry, a match indication will be generated. The match indication can be used to generate particular processing information for the packet.
Routing and switching functions can be performed by general-purpose processors that run a routing algorithm. Such an approach can result in limited throughput of data packets, be expensive in terms of component cost, and require considerable area to implement when implemented as one or more integrated circuits.
One way to address the need for faster routers is to fabricate an integrated circuit that is specialized to perform routing/switching tasks. Such application specific integrated circuits (ASICs) are designed to perform particular routing functions such as a matching function in conjunction with a random access memory (RAM). Unfortunately, because ASICs are custom manufactured products, they can also be expensive to manufacture.
One type of device that is particularly suitable for matching functions is a content addressable memory (CAM) (sometimes referred to as an xe2x80x9cassociative memoryxe2x80x9d). A CAM can include a number of data storage locations, each of which can be accessed by a corresponding address. The order in which the data values are stored varies according to the type of CAM. As just one example, in a typical xe2x80x9cbinaryxe2x80x9d CAM, data can be stored in the first available xe2x80x9cemptyxe2x80x9d location. Empty locations can be distinguished from xe2x80x9cfullxe2x80x9d (or valid) locations by a status bit associated with each storage location.
Valid locations in a binary CAM can be addressed according to the contents (data values) that they store. In a typical binary CAM matching function, a comparand value (which can be a header field or a portion thereof) can be loaded into a comparand register. The comparand value can then be compared to the data values within each valid location of the conventional binary CAM. In the event the value within the comparand register matches a value of a storage location, a match signal for the matching storage location will be generated. In the event there is more than one match, one match from the multiple matches may be selected according to predetermined priority criteria. The match indication can then be used to access other information (such as routing or packet processing information, as just two examples).
By providing for the simultaneous comparison of a comparand word value (a row of comparand bit values) with a number of data words, a rapid match function can be accomplished with a binary CAM. One drawback to conventional binary CAMs is that matching functions are typically performed on data values having a fixed number of bits. Unfortunately, many routing and switching functions can require matching a comparand value to data values having variable bit lengths. This type of matching function is often referred to as xe2x80x9clongest prefix matching.xe2x80x9d
An example of a longest prefix matching operation will now be described. Referring now to FIG. 10, an example of five CAM entries are illustrated. The five CAM entries occupy CAM addresses 0FF0 to 0FF4. Each entry stores a binary data value having a non-masked portion that can be compared to an applied comparand value. Such non-masked portions are shown as zeros and ones in FIG. 10. In addition, each data value includes a masked portion that is not compared to an applied comparand value. The masked portions are represented by a series of Xs in FIG. 10. It is understood that each X could be a 0 or 1, but is represented by an X because the digit is xe2x80x9cmaskedxe2x80x9d according to a mask value.
Data values can be masked by providing corresponding mask data. In one particular arrangement, a mask bit can be provided for each data bit. Thus, the mask data for the first twenty bits (going from left to right) of the data value at 0FF0 can have mask bits of one value (1, for example), while the remaining twelve bits can have mask bits of another value (0, for example). A conventional ternary CAM can include memory cells that store a mask bit alongside a data bit.
FIG. 10 also illustrates a comparand value CMP. As shown in the figure, the non-masked portions of entries 0FF0 and 0FF2 match corresponding portions of the comparand value. Thus, when the comparand value is applied, entries 0FF0 and 0FF2 can generate match indications.
In a longest prefix matching operation, match indications are prioritized to select the entry having the longest non-masked portion. Thus, in the example of FIG. 10, entry 0FF0 provides the longest prefix match. Conventionally, priority between variable prefix data values can be established according to the order of entries within the CAM. Thus, data values are stored in the order of prefix length. The values with the most unmasked bits can be stored as entries at the lowest addresses. An entry having a lower address will have a higher priority.
Priority between multiple match indications is typically accomplished with a priority encoder circuit. The single match indication having the highest priority may then be applied to a memory to generate an index value. In one particular conventional approach, a prioritized match indication can be applied to a read only memory to generate an associated index value. The index value may then be used to access a random access memory which can store the rest of the associated data.
The ternary CAM approach described above can provide rapid matching operations, and so can be very useful when utilized in packet processing devices.
An important issue in CAM applications, particularly for CAMs used in packet processing devices, arises when a new data value must be added to a ternary CAM. Such operations are often referred to as xe2x80x9ctable updates.xe2x80x9d In a conventional table update, new data must be stored in a location according to its prefix length.
An example of a table update is set forth in FIGS. 11A to 11C. FIGS. 11A to 11C show the same ternary CAM at different stages in a table update operation. FIG. 11A shows the CAM prior to a table update operation. The CAM is designated by the general reference character 1100 and can include consecutive entry groups 1102-1 to 1102-5. Each consecutive group (1102-1 to 1102-5) stores data values of the same prefix length. Overall, the data values are arranged in an order within the CAM 1100, with the longest prefix being at the top of the CAM 1100 and the shortest prefix being toward the bottom. Masked portions of the data values are shown by diagonal hashing lines.
In the example of FIGS. 11A to 11C, a new data value is added that has the same prefix length as the data values of consecutive group 1102-2. Because prefix length order must be maintained, a location must be made available so that the new data value can be added as another entry to consecutive group 1102-2. This is shown in FIG. 11B.
In FIG. 11B, a location is made available by shifting data values having shorter prefixes down by one location. Consequently, the former first entry of consecutive group 1102-3 is turned into an available location to store 1104.
The new data value can then be written into the available location 1104. The CAM 1100 following such a write operation is shown in FIG. 11C. The new data value is now the last entry of consecutive group 1102-2.
A drawback to the arrangement of FIGS. 11A to 11C is that, conventionally, shifting data in the manner shown in FIG. 11B can take a large number of write operations. This can consume considerable time, and in the case of data packet processing devices, may result in processing xe2x80x9cstallsxe2x80x9d as the data values are reordered in the CAM.
One approach to addressing these drawbacks associated with table update operations is to include a priority field within the CAM. Such a priority field can enable data values to be stored in a CAM in no particular order. In the event there are multiple match indications, such match indications can be sorted according to their priority field. Data values with longer prefixes will have higher priority values than those with shorter prefixes.
A drawback to CAMs with priority fields is that additional memory bit locations must be provided for such priority fields. Further, search operations can take more time as priority values will have to be sorted after a comparand is matched against the data values.
It would be desirable to arrive at some way of using ternary CAMs that can perform table update operations without the drawbacks of conventional approaches.
According to one embodiment of the present invention, a ternary content addressable memory (CAM) can have a number of entries arranged into groups. CAM data values of the same length can be stored in each group. When a new CAM data value is added to the CAM, the new data value can be stored into one of these groups according to the prefix length. Provided there are free entries in a group, a CAM data value can be added without having to reorder other data values in the CAM.
According to one aspect of the embodiments, a CAM can process a field within data packets on a data network. The field within the data packets can have various prefix lengths. Look-ups of different prefix lengths can occur with different estimated probabilities. The CAM can have a number of entries arranged into groups, each group corresponding to a prefix of a particular length. The size of a group can correspond to the general probability of the distribution of different look-ups of its associated prefix length in a network.
According to another aspect of the embodiments, a CAM can receive data values having corresponding prefix lengths. A translating circuit can receive prefix length values and provide corresponding CAM physical address values. In this way, CAM entries can be accessed according to prefix length.
According to another aspect of the embodiments, a CAM can include a storage device that stores CAM addresses corresponding to particular prefix lengths. Initially, a CAM address can be a base address for a given group of CAM entries. As a data value is added to the group, the CAM address can be incremented and stored to provide the next free address for a given group.
According to another aspect of the embodiments, a CAM can include a random access memory (RAM) having entries that store CAM address values that are accessed by corresponding prefix lengths.
According to another aspect of the embodiments, a CAM can include an encoder that receives mask values and encodes them into prefix lengths.
According to another aspect of the embodiments, a CAM can include a translator circuit that generates CAM addresses in response to an applied prefix length. A CAM address generated by a translator circuit can be incremented by a counter circuit.
According to another aspect of the embodiments, a CAM can include a translator circuit that generates CAM addresses in response to an applied prefix length. A CAM address can access a mask array or a data array according to a predetermined control signal.
According to another aspect of the embodiments, a CAM can include a number of entries arranged into fixed groups and variable groups. Fixed groups can be accessed according to a prefix length value and can store data values of the same prefix length. Variable groups can be accessed by a CAM address, and store data values having different prefix lengths.
According to another aspect of the embodiments, a CAM can include groups of entries that can store data values having predetermined prefix lengths. Prefix values can be applied to a translator circuit to generate a CAM address of the group corresponding to the prefix length. A series of data values of the prefix length can then be written into the group by a counter circuit that increments the CAM address. When the last data value of series is written into a CAM entry, the incremented CAM address can be written into the translator circuit.